package test3;

import java.util.*;
import java.util.regex.*;

public class FollowSetCalculator {
    private static final String EPSILON = "ε";

    public static void calculateFollowSets() {
        // 初始化 Follow 集合
        Map<String, Set<String>> follow = new HashMap<>();
        for (String nonTerminal : Init.V_N) {
            follow.put(nonTerminal, new HashSet<>());
        }

        // 为起始符号添加结束标记
        follow.get(Init.V_N.iterator().next()).add("$");

        boolean changed = true;
        while (changed) {
            changed = false;
            for (Map.Entry<String, Set<List<String>>> entry : Init.Production.entrySet()) {
                String nonTerminal = entry.getKey();
                for (List<String> production : entry.getValue()) {
                    for (int i = 0; i < production.size(); i++) {
                        String symbol = production.get(i);
                        if (Init.V_N.contains(symbol)) {
                            Set<String> followSet = follow.get(symbol);
                            if (i == production.size() - 1) {
                                // 最后一个符号
                                Set<String> followOfNonTerminal = follow.get(nonTerminal);
                                if (!followSet.containsAll(followOfNonTerminal)) {
                                    changed = true;
                                    followSet.addAll(followOfNonTerminal);
                                }
                            } else {
                                String nextSymbol = production.get(i + 1);
                                if (Init.V_T.contains(nextSymbol) || nextSymbol.equals(EPSILON)) {
                                    Set<String> followOfNonTerminal = follow.get(nonTerminal);
                                    if (!followSet.containsAll(followOfNonTerminal)) {
                                        changed = true;
                                        followSet.addAll(followOfNonTerminal);
                                    }
                                } else {
                                    // 非终结符后面跟着非终结符
                                    Set<String> firstOfNext = FirstSetCalculator.computeFirst(nextSymbol);
                                    if (firstOfNext.contains(EPSILON)) {
                                        // 如果下一个符号可以推出 ε，还需要添加 Follow(产生式左侧的非终结符)
                                        Set<String> followOfNonTerminal = follow.get(nonTerminal);
                                        if (!followSet.containsAll(followOfNonTerminal)) {
                                            changed = true;
                                            followSet.addAll(followOfNonTerminal);
                                        }
                                    }
                                    if (!followSet.containsAll(firstOfNext)) {
                                        changed = true;
                                        followSet.addAll(firstOfNext);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        // 输出 Follow 集合
        System.out.println("Follow Sets:");
        for (Map.Entry<String, Set<String>> entry : follow.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}
